This invention relates to decoding data that has been encoded with a Reed-Solomon code for transmission, and more specifically to decoding Reed-Solomon encoded data containing check bits.
When transmitting data from spacecraft, noise interference can be greatly reduced by encoding the data in one of the known error correcting codes. However, these codes require that extra "overhead" bits be transmitted along with the data, which reduces the rate of data transmission. Among the most sophisticated and powerful codes, the Golay and the convolutional codes require as much as a 50% overhead, thus effectively halving the data rate. Reed-Solomon codes, discussed in the article "Polynomial Codes Over Certain Finite Field" by I. S. Reed and G. Solomon, J. Soc. Industr. Appl. Math, Vol. 8, No. 2, pp 300-304, June, 1960, require fewer overhead bits and are therefore quite attractive.
Several space missions have Reed-Solomon encoders on board, and Reed-Solomon decoders on the ground, such as the Galileo Mission. However, commercial Reed-Solomon decoders are unavailable for the code format adopted for the Galileo Mission, a format which requires only a 15% overhead. Only one Reed-Solomon decoder has even been produced commercially; it operated with a different format and was too slow for the required data rate from Galileo. This decoder, described in U.S. Pat. No. 4,162,480 by Elwyn R. Berlekamp, used general purpose microcomputers to operate the decoding processes, which required a minimum of hardware but caused many internal delays during processing.
The present invention has the ability to decode three formats, including the Galileo and the potential of decoding other formats as well. The design philosophy is to use dedicated hardware for higher speed operation, and to pipeline data processing throughout, and internally within each stage as well. Although this requires more hardware than the microprocessor approach, which is tolerable on ground equipment, it eliminates delays by allowing processing to begin on a second word before it is fully completed on a first word, and calculations are more direct. In addition, the dedicated hardware can be operated at a higher clock rate than can general purpose computers.